#include <stdio.h>
#include "InsertionSort.h"

//时间: 平均O(n^2) 最坏O(n^2) 空间: O(1) 稳定 例如:4 4 2
void DirectInsertion::Iterative(int list[], int n)
{
	int j, next;
	for(int i=1; i<n; ++i) {
		next = list[i];
		for(j=i-1; j>=0 && next < list[j]; --j) {
			list[j+1] = list[j];
		}
		list[j+1] = next;
	}	
}

//时间: 平均O(n^2) 最坏O(n^2) 空间：O(n) 稳定 例如:4 4 2
void DirectInsertion::Recursive(int list[], int n)
{
	if (n > 1) {
		Recursive(list, n-1);
	}
	
	int j;	
	int next = list[n];
	for(j=n-1; j>=0 && next < list[j]; --j) {
		list[j+1] = list[j];
	}
	list[j+1] = next;					
}

//时间: 平均O(n^2) 最坏O(n^2) 空间: O(1) 稳定 例如:4 4 2
void BinaryInsertion::Iterative(int list[], int n)
{
	int next, low, high, m;
	for(int i=1; i<n; ++i) {
		next = list[i];
		low = 0, high = i-1;
		while(low <= high) {
			m = (low+high)/2;	
			if (next >= list[m]) low = m+1;
			else high = m-1; 				
		}		

		int j;
		for(j=i; j>low; --j) {
			list[j] = list[j-1];		
		}
		list[j] = next;					
	}	
}

//时间: 平均O(n^2) 最坏O(n^2) 空间：O(n) 稳定 例如:4 4 2
void BinaryInsertion::Recursive(int list[], int n)
{
	if (n >= 1) {
		Recursive(list, n-1);
	}

	int next, low, high, m;
	next = list[n];
	low = 0, high = n-1;
	while(low <= high) {
		m = (low+high)/2;	
		if (next >= list[m]) low = m+1;
		else high = m-1; 				
	}

	int j;
	for(j=n; j>low; --j) {
		list[j] = list[j-1];		
	} 				
	list[j] = next;
}

void ShellInsertion::ShellPass(int list[], int n, int d)
{
	for(int i=d; i<n; ++i) {
		int tmp = list[i];
		int j = i-d;
		while(list[j] > tmp) {
			list[j+d] = list[j];
			j -= d;	
			if (j<0) break;
		}
		list[j+d] = tmp;
	}		
}

//时间：O(n^1.25 ~ 1.65n^1.25) 空间：O(1) 不稳定
void ShellInsertion::Iterative(int list[], int n)
{
	int increment = n /2;
	while(increment >= 1) {
		ShellPass(list, n, increment);
		increment /= 2;	
	}
}

void ShellInsertion::Recursive(int list[], int n)
{
		
}
